Masala #0797

Satr chapdan o’ngga o’qilsa ham, o’ngdan chapga o’qilsa ham bir xil bo’lsa bunday satr palindrom satr deb ataladi. Masalan : «a», «aa», «obbo», «aka» va «uzbekezbu» satrlari palindrom satrdir.
$S$ satrning qism satrlari deb shu satrning barcha $1 ≤ i ≤ j ≤ |S|$ juftliklar uchun $S_i, S_{i+1}, \dots , S_j$ ketma-ketlikdan tashkil topgan satrlarga aytiladi. Misol uchun «obbo» satrida «o», «b», «b», «o», «ob», «bb», «bo», «obb», «bbo», «obbo» qism satrlar mavjud.

Sizga dastlab $S$ bo’sh satr berilgan. Siz $S$ satri ustada $Q$ ta so’rovni berilish tartibida bajarishingiz kerak.
Har bir so’rovda sizga $c(c ∈ [ − , a − z])$ belgisi kiritiladi.

✦ Agar c = ′−′ bo’lsa siz $S$ satrning oxirgi belgisini o’chirishingiz kerak(bunday holda $S$ satrda o’chirish uchun belgi borligi kafolotlanadi).

✦ Agar $c ∈ [a − z]$ bo’lsa siz $S$ satrning oxiriga berilgan belgini qo’shishingiz kerak. Har bir so’rovdan so’ng $S$ satrining qism satrlaridan nechtasi palindrom ekanligini chop eting!

Birinchi satrda bitta butun son, so’rovlar soni $Q(1 ≤ Q ≤ 10^4)$ kiritiladi.
Ikkinchi satrda Q ta belgi, ya’ni har bir so’rov uchun c belgisi bir - beridan ajratilmagan holda kiritiladi.

Yagona satrda probel bilan ajratilgan holda Q ta butun son, har bir so’rovdan so’ng S satrining qism satrlaridan nechtasi palindrom ekanligini chop etilsin!